package com.lw.leetcode.sort.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * 1334. 阈值距离内邻居最少的城市
 *
 * @author liw
 * @version 1.0
 * @date 2021/11/11 10:14
 */
public class FindTheCity {


    public static void main(String[] args) {
        FindTheCity test = new FindTheCity();


        // 3
        int a = 4;
        int[][] arr = {{0, 1, 3}, {1, 2, 1}, {1, 3, 4}, {2, 3, 1}};
        int d = 4;

        // 0
//        int a = 5;
//        int[][] arr = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
//        int d = 2;

        // 0
//        int a = 5;
//        int[][] arr = {{0, 1, 2}, {0, 4, 8}, {1, 2, 3}, {1, 4, 2}, {2, 3, 1}, {3, 4, 1}};
//        int d = 2;

        // 5
//        int a = 6;
//        int[][] arr = {{0, 1, 10}, {0, 2, 1}, {2, 3, 1}, {1, 3, 1}, {1, 4, 1}, {4, 5, 10}};
//        int d = 20;

        // 5
//        int a = 6;
//        int[][] arr = {{0,3,7},{2,4,1},{0,1,5},{2,3,10},{1,3,6},{1,2,1}};
//        int d = 417;


        int theCity = test.findTheCity(a, arr, d);
        System.out.println(theCity);

    }

    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            int c = edge[2];
            map.computeIfAbsent(a, v -> new ArrayList<>()).add((c << 8) + b);
            map.computeIfAbsent(b, v -> new ArrayList<>()).add((c << 8) + a);
        }
        PriorityQueue<Long> queue = new PriorityQueue<>();
        int[] flags = new int[n];
        int index = 0;
        int min = Integer.MAX_VALUE;
        for (int i = n - 1; i >= 0; i--) {
            Arrays.fill(flags, Integer.MAX_VALUE);
            int count = -1;
            queue.add((long) i);
            while (!queue.isEmpty()) {
                long value = queue.poll();
                long sum = value >> 32;
                int key = (int) value;
                if (sum >= flags[key]) {
                    continue;
                }
                flags[key] = (int) sum;
                List<Integer> list = map.get(key);
                if (list == null) {
                    return i;
                }
                for (int v : list) {
                    int c = v >> 8;
                    int b = v & 0XFF;
                    long s = sum + c;
                    if (s <= distanceThreshold && s < flags[b]) {
                        queue.add((s << 32) + b);
                    }
                }
            }
            for (int flag : flags) {
                if (flag != Integer.MAX_VALUE) {
                    count++;
                }
            }
            if (count == 0) {
                return i;
            }
            if (count < min) {
                min = count;
                index = i;
            }
        }
        return index;
    }

}
